#ifndef __VECTORSET_H__
#define __VECTORSET_H__

/*
===============================================================================

Vector Set

Creates a set of vectors without duplicates.

===============================================================================
*/

namespace inf {
    template< class type, int dimension >
    class VectorSet : public List<type> {
    public:
        VectorSet( void );
        VectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );

        // returns total size of allocated memory
        size_t					allocated( void ) const { return List<type>::allocated() + hash.allocated(); }
        // returns total size of allocated memory including size of type
        size_t					Size( void ) const { return sizeof( *this ) + allocated(); }

        void					Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
        void					ResizeIndex( const int newSize );
        void					clear( void );

        int						FindVector( const type &v, const float epsilon );

    private:
        HashIndex				hash;
        type					mins;
        type					maxs;
        int						boxHashSize;
        float					boxInvSize[dimension];
        float					boxHalfSize[dimension];
    };

    template< class type, int dimension >
    INF_INLINE VectorSet<type,dimension>::VectorSet( void ) {
        hash.clear( inf::math::ipow( boxHashSize, dimension ), 128 );
        boxHashSize = 16;
        memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) );
        memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) );
    }

    template< class type, int dimension >
    INF_INLINE VectorSet<type,dimension>::VectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
        Init( mins, maxs, boxHashSize, initialSize );
    }

    template< class type, int dimension >
    INF_INLINE void VectorSet<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
        int i;
        float boxSize;

        List<type>::assure_size( initialSize );
        List<type>::ready_num( 0, false );

        hash.clear( inf::math::ipow( boxHashSize, dimension ), initialSize );

        this->mins = mins;
        this->maxs = maxs;
        this->boxHashSize = boxHashSize;

        for ( i = 0; i < dimension; i++ ) {
            boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize;
            boxInvSize[i] = 1.0f / boxSize;
            boxHalfSize[i] = boxSize * 0.5f;
        }
    }

    template< class type, int dimension >
    INF_INLINE void VectorSet<type,dimension>::ResizeIndex( const int newSize ) {
        List<type>::resize( newSize );
        hash.resize_index( newSize );
    }

    template< class type, int dimension >
    INF_INLINE void VectorSet<type,dimension>::clear( void ) {
        List<type>::clear();
        hash.clear();
    }

    template< class type, int dimension >
    INF_INLINE int VectorSet<type,dimension>::FindVector( const type &v, const float epsilon ) {
        int i, j, k, hashKey, partialHashKey[dimension];

        for ( i = 0; i < dimension; i++ ) {
            assert( epsilon <= boxHalfSize[i] );
            partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] );
        }

        for ( i = 0; i < ( 1 << dimension ); i++ ) {

            hashKey = 0;
            for ( j = 0; j < dimension; j++ ) {
                hashKey *= boxHashSize;
                hashKey += partialHashKey[j] + ( ( i >> j ) & 1 );
            }

            for ( j = hash.get_first( hashKey ); j >= 0; j = hash.get_next( j ) ) {
                const type &lv = (*this)[j];
                for ( k = 0; k < dimension; k++ ) {
                    if ( inf::math::fabs( lv[k] - v[k] ) > epsilon ) {
                        break;
                    }
                }
                if ( k >= dimension ) {
                    return j;
                }
            }
        }

        hashKey = 0;
        for ( i = 0; i < dimension; i++ ) {
            hashKey *= boxHashSize;
            hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] );
        }

        hash.add( hashKey, List<type>::size() );
        append( v );
        return List<type>::size()-1;
    }


    /*
    ===============================================================================

    Vector Subset

    Creates a subset without duplicates from an existing list with vectors.

    ===============================================================================
    */

    template< class type, int dimension >
    class VectorSubset {
    public:
        VectorSubset( void );
        VectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );

        // returns total size of allocated memory
        size_t					allocated( void ) const { return List<type>::allocated() + hash.allocated(); }
        // returns total size of allocated memory including size of type
        size_t					Size( void ) const { return sizeof( *this ) + allocated(); }

        void					Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
        void					clear( void );

        // returns either vectorNum or an index to a previously found vector
        int						FindVector( const type *vectorList, const int vectorNum, const float epsilon );

    private:
        HashIndex				hash;
        type					mins;
        type					maxs;
        int						boxHashSize;
        float					boxInvSize[dimension];
        float					boxHalfSize[dimension];
    };

    template< class type, int dimension >
    INF_INLINE VectorSubset<type,dimension>::VectorSubset( void ) {
        hash.clear( inf::math::ipow( boxHashSize, dimension ), 128 );
        boxHashSize = 16;
        memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) );
        memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) );
    }

    template< class type, int dimension >
    INF_INLINE VectorSubset<type,dimension>::VectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
        Init( mins, maxs, boxHashSize, initialSize );
    }

    template< class type, int dimension >
    INF_INLINE void VectorSubset<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
        int i;
        float boxSize;

        hash.clear( inf::math::ipow( boxHashSize, dimension ), initialSize );

        this->mins = mins;
        this->maxs = maxs;
        this->boxHashSize = boxHashSize;

        for ( i = 0; i < dimension; i++ ) {
            boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize;
            boxInvSize[i] = 1.0f / boxSize;
            boxHalfSize[i] = boxSize * 0.5f;
        }
    }

    template< class type, int dimension >
    INF_INLINE void VectorSubset<type,dimension>::clear( void ) {
        List<type>::clear();
        hash.clear();
    }

    template< class type, int dimension >
    INF_INLINE int VectorSubset<type,dimension>::FindVector( const type *vectorList, const int vectorNum, const float epsilon ) {
        int i, j, k, hashKey, partialHashKey[dimension];
        const type &v = vectorList[vectorNum];

        for ( i = 0; i < dimension; i++ ) {
            assert( epsilon <= boxHalfSize[i] );
            partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] );
        }

        for ( i = 0; i < ( 1 << dimension ); i++ ) {

            hashKey = 0;
            for ( j = 0; j < dimension; j++ ) {
                hashKey *= boxHashSize;
                hashKey += partialHashKey[j] + ( ( i >> j ) & 1 );
            }

            for ( j = hash.get_first( hashKey ); j >= 0; j = hash.get_next( j ) ) {
                const type &lv = vectorList[j];
                for ( k = 0; k < dimension; k++ ) {
                    if ( inf::math::fabs( lv[k] - v[k] ) > epsilon ) {
                        break;
                    }
                }
                if ( k >= dimension ) {
                    return j;
                }
            }
        }

        hashKey = 0;
        for ( i = 0; i < dimension; i++ ) {
            hashKey *= boxHashSize;
            hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] );
        }

        hash.add( hashKey, vectorNum );
        return vectorNum;
    }

}   // ::inf

#endif /* !__VECTORSET_H__ */
